home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / graphicgems4.lha / GemsIV / ptpoly_haines / p_test.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-06  |  23.6 KB  |  927 lines
  1. /* p_test.c - point in polygon inside/outside tester.  This is
  2.  * simply testing and display code, the actual algorithms are in ptinpoly.c.
  3.  *
  4.  * Probably the most important thing to set for timings is TEST_RATIO (too
  5.  * low and the timings are untrustworthy, too high and you wait forever).
  6.  * Start low and see how consistent separate runs appear to be.
  7.  *
  8.  * To add a new algorithm to the test suite, add code at the spots marked
  9.  * with '+++'.
  10.  *
  11.  * See USAGE for command line options (or just do "p_test -?").
  12.  *
  13.  * by Eric Haines, 3D/Eye Inc, erich@eye.com
  14.  */
  15.  
  16. /* Define TIMER to perform timings on code (need system timing function) */
  17. /* #define TIMER */
  18.  
  19. /* Number of times to try a single point vs. a polygon, per vertex.
  20.  * This should be greater than 1 / ( HZ * approx. single test time in seconds )
  21.  * in order to get a meaningful timings difference.  200 is reasonable for a
  22.  * IBM PC 25 MHz 386 with no FPU, 50000 is good for an HP 720 workstation.
  23.  * Start low and see how consistent separate runs appear to be.
  24.  */
  25.  
  26. #ifdef    TIMER
  27. #define MACHINE_TEST_RATIO    50000
  28. #else
  29. #define MACHINE_TEST_RATIO        1
  30. #endif
  31.  
  32. /* ===========    that's all the easy stuff than can be changed  ============ */
  33.  
  34. #include <stdio.h>
  35. #include <stdlib.h>
  36. #include <math.h>
  37. #include "ptinpoly.h"
  38.  
  39. #ifdef    TIMER
  40. #ifdef    IBM_PC
  41. #include <bios.h>
  42. #include <time.h>
  43. #define HZ    CLK_TCK
  44. #define mGetTime(t)    (t) = biostime(0,0L) ;
  45.  
  46. #else    /* UNIX */
  47. #include <sys/types.h>
  48. #include <sys/param.h>
  49. #include <sys/times.h>
  50. struct    tms    Timebuf ;
  51.  
  52. #define mGetTime(t)    (t) = times(&Timebuf) ;
  53.  
  54. /* for Sun and others do something like:
  55. #define mGetTime(t)    times(&Timebuf) ;                \
  56.             (t) = Timebuf.tms_utime + Timebuf.tms_stime ;
  57. */
  58.  
  59. #endif
  60. #endif
  61.  
  62. #ifdef    DISPLAY
  63. #include <starbase.c.h>        /* HP display */
  64. #endif
  65.  
  66. #ifndef TRUE
  67. #define TRUE    1
  68. #define FALSE    0
  69. #endif
  70.  
  71. #ifndef HUGE
  72. #define HUGE    1.79769313486232e+308
  73. #endif
  74.  
  75. #define X    0
  76. #define Y    1
  77.  
  78. #ifdef    DISPLAY
  79. int    Display_Tests = 0 ;
  80. double    Display_Scale ;
  81. double    Display_OffsetX ;
  82. double    Display_OffsetY ;
  83. int    Fd ;
  84. #endif
  85.  
  86. #define USAGE    \
  87. /* +++ add new routine here +++ */\
  88. printf("p_test [options] -{ABCEGIPSTW}\n");\
  89. printf("  -v minverts [maxverts] = variation in number of polygon vertices\n");\
  90. printf("  -r radius = radius of polygon vertices generated\n");\
  91. printf("  -p perturbation = perturbation of polygon vertices generated\n");\
  92. printf("       These first three determine the type of polygon tested.\n");\
  93. printf("       No perturbation gives regular polygons, while no radius\n");\
  94. printf("       gives random polygons, and a mix gives semi-random polygons\n");\
  95. printf("  -s size = scale of test point box around polygon (1.0 default)\n");\
  96. printf("       A larger size means more points generated outside the\n");\
  97. printf("       polygon.     By default test points are in the bounding box.\n");\
  98. printf("  -b bins = number of y bins for trapezoid test\n");\
  99. printf("  -g resolution = grid resolution for grid test\n");\
  100. printf("  -n polygons = number of polygons to test (default %d)\n",\
  101.         Test_Polygons);\
  102. printf("  -i points = number of points to test per polygon (default %d)\n",\
  103.         Test_Points);\
  104. printf("  -c increment = constrain polygon and test points to grid\n");\
  105. /* +++ add new routine here +++ */\
  106. printf("  -{ABCEGIPSTW} = angle/bary/crossings/exterior/grid/inclusion/\n");\
  107. printf("       plane/spackman/trapezoid (bin)/weiler test (default is all)\n");\
  108. printf("  -d = display polygons and points using starbase\n");
  109.  
  110.  
  111. typedef struct {
  112.     double    time_total ;
  113.     int    test_ratio ;
  114.     int    test_times ;
  115.     int    work ;
  116.     char    *name ;
  117.     int    flag ;
  118. } Statistics, *pStatistics ;
  119.  
  120. #define ANGLE_TEST         0
  121. #define BARYCENTRIC_TEST     1
  122. #define CROSSINGS_TEST         2
  123. #define EXTERIOR_TEST         3
  124. #define GRID_TEST         4
  125. #define INCLUSION_TEST         5
  126. #define PLANE_TEST         6
  127. #define SPACKMAN_TEST         7
  128. #define TRAPEZOID_TEST         8
  129. #define WEILER_TEST         9
  130. /* +++ add new name here and increment TOT_NUM_TESTS +++ */
  131. #define TOT_NUM_TESTS         10
  132.  
  133. Statistics    St[TOT_NUM_TESTS] ;
  134.  
  135. char    *TestName[] = {
  136.     "angle",
  137.     "barycentric",
  138.     "crossings",
  139.     "exterior",
  140.     "grid",
  141.     "inclusion",
  142.     "plane",
  143.     "spackman",
  144.     "trapezoid",
  145.     "weiler" } ;
  146. /* +++ add new name here +++ */
  147.  
  148. /* minimum & maximum number of polygon vertices to generate */
  149. #define TOT_VERTS    1000
  150. static int    Min_Verts = 3 ;
  151. static int    Max_Verts = 6 ;
  152.  
  153. /* Test polygons are generated by going CCW in a circle around the origin from
  154.  * the X+ axis around and generating vertices.    The radius is how big the
  155.  * circumscribing circle is, the perturbation is how much each vertex is varied.
  156.  * So, radius 1 and perturbation 0 gives a regular, inscribed polygon;
  157.  * radius 0 and perturbation 1 gives a totally random polygon in the
  158.  * space [-1,1)
  159.  */
  160. static double    Vertex_Radius = 1.0 ;
  161. static double    Vertex_Perturbation = 0.0 ;
  162.  
  163. /* A box is circumscribed around the test polygon.  Making this box bigger
  164.  * is useful for a higher rejection rate.  For example, a ray tracing bounding
  165.  * box usually contains a few polygons, so making the box ratio say 2 or so
  166.  * could simulate this type of box.
  167.  */
  168. static double    Box_Ratio = 1.0 ;
  169.  
  170. /* for debugging purposes, you might want to set Test_Polygons and Test_Points
  171.  * high (say 1000), and then set the *_Test_Times to 1.     The timings will be
  172.  * useless, but you'll test 1000 polygons each with 1000 points.  You'll also
  173.  * probably want to set the Vertex_Perturbation to something > 0.0.
  174.  */
  175. /* number of different polygons to try - I like 50 or so; left low for now */
  176. static int    Test_Polygons = 20 ;
  177.  
  178. /* number of different intersection points to try - I like 50 or so */
  179. static int    Test_Points = 20 ;
  180.  
  181. /* for debugging or constrained test purposes, this value constrains the value
  182.  * of the polygon points and the test points to those on a grid emanating from
  183.  * the origin with this increment.  Points are shifted to the closest grid
  184.  * point.  0.0 means no grid.  NOTE:  by setting this value, a large number
  185.  * of points will be generated exactly on interior (triangle fan) or exterior
  186.  * edges.  Interior edge points will cause problems for the algorithms that
  187.  * generate interior edges (triangle fan).  "On edge" points are arbitrarily
  188.  * determined to be inside or outside the polygon, so results can differ.
  189.  */
  190. static double    Constraint_Increment = 0.0 ;
  191.  
  192. /* default resolutions */
  193. static    int    Grid_Resolution = 20 ;
  194. static    int    Trapezoid_Bins = 20 ;
  195.  
  196. #define Max(a,b)    (((a)>(b))?(a):(b))
  197.  
  198. #define FPRINTF_POLYGON                        \
  199.         fprintf( stderr, "point %g %g\n",        \
  200.             (float)point[X], (float)point[Y] ) ;    \
  201.         fprintf( stderr, "polygon (%d vertices):\n",    \
  202.             numverts ) ;                \
  203.         for ( n = 0 ; n < numverts ; n++ ) {        \
  204.             fprintf( stderr, "    %g %g\n",        \
  205.             (float)pgon[n][X], (float)pgon[n][Y]);    \
  206.         }
  207.  
  208. /* timing functions */
  209. #ifdef    TIMER
  210.  
  211. #define START_TIMER( test_id )                        \
  212.     /* do the test a bunch of times to get a useful time reading */ \
  213.     mGetTime( timestart ) ;                        \
  214.     for ( tcnt = St[test_id].test_times+1 ; --tcnt ; )
  215.  
  216. #define STOP_TIMER( test_id )                        \
  217.     mGetTime( timestop ) ;                        \
  218.     /* time in microseconds */                    \
  219.     St[test_id].time_total +=                    \
  220.         1000000.0 * (double)(timestop - timestart) /        \
  221.         (double)(HZ * St[test_id].test_times) ;
  222. #else
  223. #define START_TIMER( test_id )
  224. #define STOP_TIMER( test_id )
  225. #endif
  226.  
  227. char    *getenv() ;
  228. void    ScanOpts() ;
  229. void    ConstrainPoint() ;
  230. void    BreakString() ;
  231. #ifdef    DISPLAY
  232. void    DisplayPolygon() ;
  233. void    DisplayPoint() ;
  234. #endif
  235.  
  236.  
  237. /* test program - see USAGE for command line options */
  238. main(argc,argv)
  239. int argc;  char *argv[];
  240. {
  241. #ifdef    TIMER
  242. register long    tcnt ;
  243. long    timestart ;
  244. long    timestop ;
  245. #endif
  246.  
  247. int    i, j, k, n, numverts, inside_flag, inside_tot, numrec ;
  248. double    pgon[TOT_VERTS][2], point[2], angle, ran_offset ;
  249. double    rangex, rangey, scale, minx, maxx, diffx, miny, maxy, diffy ;
  250. double    offx, offy ;
  251. char    str[256], *strplus ;
  252. GridSet grid_set ;
  253. pPlaneSet    p_plane_set ;
  254. pSpackmanSet    p_spackman_set ;
  255. TrapezoidSet    trap_set ;
  256.  
  257. #ifdef    CONVEX
  258. pPlaneSet    p_ext_set ;
  259. pInclusionAnchor    p_inc_anchor ;
  260. #endif
  261.  
  262.     SRAN() ;
  263.  
  264.     ScanOpts( argc, argv ) ;
  265.  
  266.     for ( i = 0 ; i < TOT_NUM_TESTS ; i++ ) {
  267.     St[i].time_total = 0.0 ;
  268.     if ( i == ANGLE_TEST ) {
  269.         /* angle test is real slow, so test it fewer times */
  270.         St[i].test_ratio = MACHINE_TEST_RATIO / 10 ;
  271.     } else {
  272.         St[i].test_ratio = MACHINE_TEST_RATIO ;
  273.     }
  274.     St[i].name = TestName[i] ;
  275.     St[i].flag = 0 ;
  276.     }
  277.  
  278.     inside_tot = 0 ;
  279.  
  280. #ifdef    CONVEX
  281.     if ( Vertex_Perturbation > 0.0 && Max_Verts > 3 ) {
  282.     fprintf( stderr,
  283.         "warning: vertex perturbation is > 0.0, which is exciting\n");
  284.     fprintf( stderr,
  285.         "    when using convex-only algorithms!\n" ) ;
  286.     }
  287. #endif
  288.  
  289.     if ( Min_Verts == Max_Verts ) {
  290.     sprintf( str, "\nPolygons with %d vertices, radius %g, "
  291.         "perturbation +/- %g, bounding box scale %g",
  292.         Min_Verts, Vertex_Radius, Vertex_Perturbation, Box_Ratio ) ;
  293.     } else {
  294.     sprintf( str, "\nPolygons with %d to %d vertices, radius %g, "
  295.         "perturbation +/- %g, bounding box scale %g",
  296.         Min_Verts, Max_Verts, Vertex_Radius, Vertex_Perturbation,
  297.         Box_Ratio ) ;
  298.     }
  299.     strplus = &str[strlen(str)] ;
  300.     if ( St[TRAPEZOID_TEST].work ) {
  301.     sprintf( strplus, ", %d trapezoid bins", Trapezoid_Bins ) ;
  302.     strplus = &str[strlen(str)] ;
  303.     }
  304.     if ( St[GRID_TEST].work ) {
  305.     sprintf( strplus, ", %d grid resolution", Grid_Resolution ) ;
  306.     strplus = &str[strlen(str)] ;
  307.     }
  308. #ifdef    CONVEX
  309.     sprintf( strplus, ", convex" ) ;
  310.     strplus = &str[strlen(str)] ;
  311. #ifdef    HYBRID
  312.     sprintf( strplus, ", hybrid" ) ;
  313.     strplus = &str[strlen(str)] ;
  314. #endif
  315. #endif
  316. #ifdef    SORT
  317.     if ( St[PLANE_TEST].work || St[SPACKMAN_TEST].work ) {
  318.     sprintf( strplus, ", using triangles sorted by edge lengths" ) ;
  319.     strplus = &str[strlen(str)] ;
  320. #ifdef    CONVEX
  321.     sprintf( strplus, " and areas" ) ;
  322.     strplus = &str[strlen(str)] ;
  323. #endif
  324.     }
  325. #endif
  326. #ifdef    RANDOM
  327.     if ( St[EXTERIOR_TEST].work ) {
  328.     sprintf( strplus, ", exterior edges' order randomized" ) ;
  329.     strplus = &str[strlen(str)] ;
  330.     }
  331. #endif
  332.     sprintf( strplus, ".\n" ) ;
  333.     strplus = &str[strlen(str)] ;
  334.     BreakString( str ) ;
  335.     printf( "%s", str ) ;
  336.  
  337.     printf(
  338.     " Testing %d polygons with %d points\n", Test_Polygons, Test_Points ) ;
  339.  
  340. #ifdef    TIMER
  341.     printf( "doing timings" ) ;
  342.     fflush( NULL ) ;
  343. #endif
  344.     for ( i = 0 ; i < Test_Polygons ; i++ ) {
  345.  
  346.     /* make an arbitrary polygon fitting 0-1 range in x and y */
  347.     numverts = Min_Verts +
  348.         (int)(RAN01() * (double)(Max_Verts-Min_Verts+1)) ;
  349.  
  350.     /* add a random offset to the angle so that each polygon is not in
  351.      * some favorable (or unfavorable) alignment.
  352.      */
  353.     ran_offset = 2.0 * M_PI * RAN01() ;
  354.     minx = miny =  99999.0 ;
  355.     maxx = maxy = -99999.0 ;
  356.     for ( j = 0 ; j < numverts ; j++ ) {
  357.         angle = 2.0 * M_PI * (double)j / (double)numverts + ran_offset ;
  358.         pgon[j][X] = cos(angle) * Vertex_Radius +
  359.         ( RAN01() * 2.0 - 1.0 ) * Vertex_Perturbation ;
  360.         pgon[j][Y] = sin(angle) * Vertex_Radius +
  361.         ( RAN01() * 2.0 - 1.0 ) * Vertex_Perturbation ;
  362.  
  363.         ConstrainPoint( pgon[j] ) ;
  364.  
  365.         if ( pgon[j][X] < minx ) minx = pgon[j][X] ;
  366.         if ( pgon[j][X] > maxx ) maxx = pgon[j][X] ;
  367.         if ( pgon[j][Y] < miny ) miny = pgon[j][Y] ;
  368.         if ( pgon[j][Y] > maxy ) maxy = pgon[j][Y] ;
  369.     }
  370.  
  371.     offx = ( maxx + minx ) / 2.0 ;
  372.     offy = ( maxy + miny ) / 2.0 ;
  373.     if ( (diffx = maxx - minx ) > ( diffy = maxy - miny ) ) {
  374.         scale = 2.0 / (Box_Ratio * diffx) ;
  375.         rangex = 1.0 ;
  376.         rangey = diffy / diffx ;
  377.     } else {
  378.         scale = 2.0 / (Box_Ratio * diffy) ;
  379.         rangex = diffx / diffy ;
  380.         rangey = 1.0 ;
  381.     }
  382.  
  383.     for ( j = 0 ; j < numverts ; j++ ) {
  384.         pgon[j][X] = ( pgon[j][X] - offx ) * scale ;
  385.         pgon[j][Y] = ( pgon[j][Y] - offy ) * scale ;
  386.     }
  387.  
  388.     /* Set up number of times to test a point against a polygon, for
  389.      * the sake of getting a reasonable timing.  We already know how
  390.      * most of these will perform, so scale their # tests accordingly.
  391.      */
  392.     for ( j = 0 ; j < TOT_NUM_TESTS ; j++ ) {
  393.         if ( ( j == GRID_TEST ) || ( j == TRAPEZOID_TEST ) ) {
  394.         St[j].test_times = Max( St[j].test_ratio /
  395.             (int)sqrt((double)numverts), 1 ) ;
  396.         } else {
  397.         St[j].test_times = Max( St[j].test_ratio / numverts, 1 ) ;
  398.         }
  399.     }
  400.  
  401.     /* set up tests */
  402. #ifdef    CONVEX
  403.     if ( St[EXTERIOR_TEST].work ) {
  404.         p_ext_set = ExteriorSetup( pgon, numverts ) ;
  405.     }
  406. #endif
  407.  
  408.     if ( St[GRID_TEST].work ) {
  409.         GridSetup( pgon, numverts, Grid_Resolution, &grid_set ) ;
  410.     }
  411.  
  412. #ifdef    CONVEX
  413.     if ( St[INCLUSION_TEST].work ) {
  414.         p_inc_anchor = InclusionSetup( pgon, numverts ) ;
  415.     }
  416. #endif
  417.  
  418.     if ( St[PLANE_TEST].work ) {
  419.         p_plane_set = PlaneSetup( pgon, numverts ) ;
  420.     }
  421.  
  422.     if ( St[SPACKMAN_TEST].work ) {
  423.         p_spackman_set = SpackmanSetup( pgon, numverts, &numrec ) ;
  424.     }
  425.  
  426.     if ( St[TRAPEZOID_TEST].work ) {
  427.         TrapezoidSetup( pgon, numverts, Trapezoid_Bins, &trap_set ) ;
  428.     }
  429.  
  430. #ifdef    DISPLAY
  431.     if ( Display_Tests ) {
  432.         DisplayPolygon( pgon, numverts, i ) ;
  433.     }
  434. #endif
  435.  
  436.     /* now try # of points against it */
  437.     for ( j = 0 ; j < Test_Points ; j++ ) {
  438.         point[X] = RAN01() * rangex * 2.0 - rangex ;
  439.         point[Y] = RAN01() * rangey * 2.0 - rangey ;
  440.  
  441.         ConstrainPoint( point ) ;
  442.  
  443. #ifdef    DISPLAY
  444.         if ( Display_Tests ) {
  445.         DisplayPoint( point, TRUE ) ;
  446.         }
  447. #endif
  448.  
  449.         if ( St[ANGLE_TEST].work ) {
  450.         START_TIMER( ANGLE_TEST )
  451.             St[ANGLE_TEST].flag = AngleTest( pgon, numverts, point ) ;
  452.         STOP_TIMER( ANGLE_TEST )
  453.         }
  454.         if ( St[BARYCENTRIC_TEST].work ) {
  455.         START_TIMER( BARYCENTRIC_TEST )
  456.             St[BARYCENTRIC_TEST].flag =
  457.                 BarycentricTest( pgon, numverts, point ) ;
  458.         STOP_TIMER( BARYCENTRIC_TEST )
  459.         }
  460.         if ( St[CROSSINGS_TEST].work ) {
  461.         START_TIMER( CROSSINGS_TEST )
  462.             St[CROSSINGS_TEST].flag =
  463.                 CrossingsTest( pgon, numverts, point ) ;
  464.         STOP_TIMER( CROSSINGS_TEST )
  465.         }
  466. #ifdef    CONVEX
  467.         if ( St[EXTERIOR_TEST].work ) {
  468.         START_TIMER( EXTERIOR_TEST )
  469.             St[EXTERIOR_TEST].flag =
  470.                 ExteriorTest( p_ext_set, numverts, point );
  471.         STOP_TIMER( EXTERIOR_TEST )
  472.         }
  473. #endif
  474.         if ( St[GRID_TEST].work ) {
  475.         START_TIMER( GRID_TEST )
  476.             St[GRID_TEST].flag = GridTest( &grid_set, point ) ;
  477.         STOP_TIMER( GRID_TEST )
  478.         }
  479. #ifdef    CONVEX
  480.         if ( St[INCLUSION_TEST].work ) {
  481.         START_TIMER( INCLUSION_TEST )
  482.             St[INCLUSION_TEST].flag =
  483.                 InclusionTest( p_inc_anchor, point );
  484.         STOP_TIMER( INCLUSION_TEST )
  485.         }
  486. #endif
  487.         if ( St[PLANE_TEST].work ) {
  488.         START_TIMER( PLANE_TEST )
  489.             St[PLANE_TEST].flag =
  490.                 PlaneTest( p_plane_set, numverts, point ) ;
  491.         STOP_TIMER( PLANE_TEST )
  492.         }
  493.         if ( St[SPACKMAN_TEST].work ) {
  494.         START_TIMER( SPACKMAN_TEST )
  495.             St[SPACKMAN_TEST].flag =
  496.             SpackmanTest( pgon[0], p_spackman_set, numrec, point ) ;
  497.         STOP_TIMER( SPACKMAN_TEST )
  498.         }
  499.         if ( St[TRAPEZOID_TEST].work ) {
  500.         START_TIMER( TRAPEZOID_TEST )
  501.             St[TRAPEZOID_TEST].flag =
  502.                 TrapezoidTest( pgon, numverts, &trap_set, point ) ;
  503.         STOP_TIMER( TRAPEZOID_TEST )
  504.         }
  505.         if ( St[WEILER_TEST].work ) {
  506.         START_TIMER( WEILER_TEST )
  507.             St[WEILER_TEST].flag =
  508.                 WeilerTest( pgon, numverts, point ) ;
  509.         STOP_TIMER( WEILER_TEST )
  510.         }
  511. /* +++ add new procedure call here +++ */
  512.  
  513.         /* reality check if crossings test is used */
  514.         if ( St[CROSSINGS_TEST].work ) {
  515.         for ( k = 0 ; k < TOT_NUM_TESTS ; k++ ) {
  516.             if ( St[k].work &&
  517.                 ( St[k].flag != St[CROSSINGS_TEST].flag ) ) {
  518.             fprintf( stderr,
  519.                 "%s test says %s, crossings test says %s\n",
  520.                 St[k].name,
  521.                 St[k].flag ? "INSIDE" : "OUTSIDE",
  522.                 St[CROSSINGS_TEST].flag ? "INSIDE" : "OUTSIDE" ) ;
  523.             FPRINTF_POLYGON ;
  524.             }
  525.         }
  526.         }
  527.  
  528.         /* see if any flag is TRUE (i.e. the test point is inside) */
  529.         for ( k = 0, inside_flag = 0
  530.         ; k < TOT_NUM_TESTS && !inside_flag
  531.         ; k++ ) {
  532.         inside_flag = St[k].flag ;
  533.         }
  534.         inside_tot += inside_flag ;
  535.  
  536.         /* turn off highlighting for this point */
  537. #ifdef    DISPLAY
  538.         if ( Display_Tests ) {
  539.         DisplayPoint( point, FALSE ) ;
  540.         }
  541. #endif
  542.     }
  543.  
  544.     /* clean up test structures */
  545. #ifdef    CONVEX
  546.     if ( St[EXTERIOR_TEST].work ) {
  547.         ExteriorCleanup( p_ext_set ) ;
  548.         p_ext_set = NULL ;
  549.     }
  550. #endif
  551.  
  552.     if ( St[GRID_TEST].work ) {
  553.         GridCleanup( &grid_set ) ;
  554.     }
  555.  
  556. #ifdef    CONVEX
  557.     if ( St[INCLUSION_TEST].work ) {
  558.         InclusionCleanup( p_inc_anchor ) ;
  559.         p_inc_anchor = NULL ;
  560.     }
  561. #endif
  562.  
  563.     if ( St[PLANE_TEST].work ) {
  564.         PlaneCleanup( p_plane_set ) ;
  565.         p_plane_set = NULL ;
  566.     }
  567.  
  568.     if ( St[SPACKMAN_TEST].work ) {
  569.         SpackmanCleanup( p_spackman_set ) ;
  570.         p_spackman_set = NULL ;
  571.     }
  572.  
  573.     if ( St[TRAPEZOID_TEST].work ) {
  574.         TrapezoidCleanup( &trap_set ) ;
  575.     }
  576.  
  577. #ifdef    TIMER
  578.     /* print a "." every polygon done to give the user a warm feeling */
  579.     printf( "." ) ;
  580.     fflush( NULL ) ;
  581. #endif
  582.     }
  583.  
  584.     printf( "\n%g %% of all points were inside polygons\n",
  585.     (float)inside_tot * 100.0 / (float)(Test_Points*Test_Polygons) ) ;
  586.  
  587. #ifdef    TIMER
  588.     for ( i = 0 ; i < TOT_NUM_TESTS ; i++ ) {
  589.     if ( St[i].work ) {
  590.         printf( "  %s test time: %g microseconds per test\n",
  591.         St[i].name,
  592.         (float)( St[i].time_total/(double)(Test_Points*Test_Polygons) ) ) ;
  593.     }
  594.     }
  595. #endif
  596.  
  597.     return 0 ;
  598. }
  599.  
  600. void    ScanOpts( argc, argv )
  601. int argc;  char *argv[];
  602. {
  603. float    f1 ;
  604. int    i1 ;
  605. int    test_flag = FALSE ;
  606.  
  607.     for ( argc--, argv++; argc > 0; argc--, argv++ ) {
  608.     if ( **argv == '-' ) {
  609.         switch ( *++(*argv)) {
  610.  
  611.         case 'v':    /* vertex min & max */
  612.         argv++ ; argc-- ;
  613.         if ( argc && sscanf ( *argv, "%d", &i1 ) == 1 ) {
  614.             Min_Verts = i1 ;
  615.             argv++ ; argc-- ;
  616.             if ( argc && sscanf ( *argv, "%d", &i1 ) == 1 ) {
  617.             Max_Verts = i1 ;
  618.             } else {
  619.             argv-- ; argc++ ;
  620.             Max_Verts = Min_Verts ;
  621.             }
  622.         } else {
  623.             USAGE ;
  624.             exit(1) ;
  625.         }
  626.         break;
  627.  
  628.         case 'r':    /* vertex radius */
  629.         argv++ ; argc-- ;
  630.         if ( argc && sscanf ( *argv, "%f", &f1 ) == 1 ) {
  631.             Vertex_Radius = (double)f1 ;
  632.         } else {
  633.             USAGE ;
  634.             exit(1) ;
  635.         }
  636.         break;
  637.  
  638.         case 'p':    /* vertex perturbation */
  639.         argv++ ; argc-- ;
  640.         if ( argc && sscanf ( *argv, "%f", &f1 ) == 1 ) {
  641.             Vertex_Perturbation = (double)f1 ;
  642.         } else {
  643.             USAGE ;
  644.             exit(1) ;
  645.         }
  646.         break;
  647.  
  648.         case 's':    /* centered box size ratio - higher is bigger */
  649.         argv++ ; argc-- ;
  650.         if ( argc && sscanf ( *argv, "%f", &f1 ) == 1 ) {
  651.             Box_Ratio = (double)f1 ;
  652.             if ( Box_Ratio < 1.0 ) {
  653.             fprintf(stderr,"warning: ratio is smaller than 1.0\n");
  654.             }
  655.         } else {
  656.             USAGE ;
  657.             exit(1) ;
  658.         }
  659.         break;
  660.  
  661.         case 'b':    /* number of bins for trapezoid test */
  662.         argv++ ; argc-- ;
  663.         if ( argc && sscanf ( *argv, "%d", &i1 ) == 1 ) {
  664.             Trapezoid_Bins = i1 ;
  665.         } else {
  666.             USAGE ;
  667.             exit(1) ;
  668.         }
  669.         break;
  670.  
  671.         case 'g':    /* grid resolution for grid test */
  672.         argv++ ; argc-- ;
  673.         if ( argc && sscanf ( *argv, "%d", &i1 ) == 1 ) {
  674.             Grid_Resolution = i1 ;
  675.         } else {
  676.             USAGE ;
  677.             exit(1) ;
  678.         }
  679.         break;
  680.  
  681.         case 'n':    /* number of polygons to test */
  682.         argv++ ; argc-- ;
  683.         if ( argc && sscanf ( *argv, "%d", &i1 ) == 1 ) {
  684.             Test_Polygons = i1 ;
  685.         } else {
  686.             USAGE ;
  687.             exit(1) ;
  688.         }
  689.         break;
  690.  
  691.         case 'i':    /* number of intersections per polygon to test */
  692.         argv++ ; argc-- ;
  693.         if ( argc && sscanf ( *argv, "%d", &i1 ) == 1 ) {
  694.             Test_Points = i1 ;
  695.         } else {
  696.             USAGE ;
  697.             exit(1) ;
  698.         }
  699.         break;
  700.  
  701.         case 'c':    /* constrain increment (0 means don't use) */
  702.         argv++ ; argc-- ;
  703.         if ( argc && sscanf ( *argv, "%f", &f1 ) == 1 ) {
  704.             Constraint_Increment = (double)f1 ;
  705.         } else {
  706.             USAGE ;
  707.             exit(1) ;
  708.         }
  709.         break;
  710.  
  711.         case 'd':    /* display polygon & test points */
  712. #ifdef    DISPLAY
  713.         Display_Tests = 1 ;
  714. #else
  715.         fprintf( stderr,
  716.             "warning: display mode not compiled in - ignored\n" ) ;
  717. #endif
  718.         break;
  719.  
  720.         /* +++ add new symbol here +++ */
  721.         case 'A':    /* do tests specified */
  722.         case 'B':
  723.         case 'C':
  724.         case 'E':
  725.         case 'G':
  726.         case 'I':
  727.         case 'P':
  728.         case 'S':
  729.         case 'T':
  730.         case 'W':
  731.         test_flag = TRUE ;
  732.         if ( strchr( *argv, 'A' ) ) {
  733.             St[ANGLE_TEST].work = 1 ;
  734.         }
  735.         if ( strchr( *argv, 'B' ) ) {
  736.             St[BARYCENTRIC_TEST].work = 1 ;
  737.         }
  738.         if ( strchr( *argv, 'C' ) ) {
  739.             St[CROSSINGS_TEST].work = 1 ;
  740.         }
  741.         if ( strchr( *argv, 'E' ) ) {
  742. #ifdef    CONVEX
  743.             St[EXTERIOR_TEST].work = 1 ;
  744. #else
  745.             fprintf( stderr,
  746.             "warning: exterior test for -DCONVEX only - ignored\n" ) ;
  747. #endif
  748.         }
  749.         if ( strchr( *argv, 'G' ) ) {
  750.             St[GRID_TEST].work = 1 ;
  751.         }
  752.         if ( strchr( *argv, 'I' ) ) {
  753. #ifdef    CONVEX
  754.             St[INCLUSION_TEST].work = 1 ;
  755. #else
  756.             fprintf( stderr,
  757.             "warning: inclusion test for -DCONVEX only - ignored\n" ) ;
  758. #endif
  759.         }
  760.         if ( strchr( *argv, 'P' ) ) {
  761.             St[PLANE_TEST].work = 1 ;
  762.         }
  763.         if ( strchr( *argv, 'S' ) ) {
  764.             St[SPACKMAN_TEST].work = 1 ;
  765.         }
  766.         if ( strchr( *argv, 'T' ) ) {
  767.             St[TRAPEZOID_TEST].work = 1 ;
  768.         }
  769.         if ( strchr( *argv, 'W' ) ) {
  770.             St[WEILER_TEST].work = 1 ;
  771.         }
  772.         /* +++ add new symbol test here +++ */
  773.         break;
  774.  
  775.         default:
  776.         USAGE ;
  777.         exit(1) ;
  778.         break ;
  779.         }
  780.  
  781.     } else {
  782.         USAGE ;
  783.         exit(1) ;
  784.     }
  785.     }
  786.  
  787.     if ( !test_flag ) {
  788.     fprintf( stderr,
  789.         "error: no point in polygon tests were specified, e.g. -PCS\n" ) ;
  790.     USAGE ;
  791.     exit(1) ;
  792.     }
  793. }
  794.  
  795. void ConstrainPoint( pt )
  796. double    *pt ;
  797. {
  798. double    val ;
  799.  
  800.     if ( Constraint_Increment > 0.0 ) {
  801.     pt[X] -=
  802.         ( val = fmod( pt[X], Constraint_Increment ) ) ;
  803.     if ( fabs(val) > Constraint_Increment * 0.5 ) {
  804.         pt[X] += (val > 0.0) ? Constraint_Increment :
  805.                     -Constraint_Increment ;
  806.     }
  807.     pt[Y] -=
  808.         ( val = fmod( pt[Y], Constraint_Increment ) ) ;
  809.     if ( fabs(val) > Constraint_Increment * 0.5 ) {
  810.         pt[Y] += (val > 0.0) ? Constraint_Increment :
  811.                     -Constraint_Increment ;
  812.     }
  813.     }
  814. }
  815.  
  816. /* break long strings into 80 or less character output.     Not foolproof, but
  817.  * good enough.
  818.  */
  819. void BreakString( str )
  820. char    *str ;
  821. {
  822. int    length, i, last_space, col ;
  823.  
  824.     length = strlen( str ) ;
  825.     last_space = 0 ;
  826.     col = 0 ;
  827.     for ( i = 0 ; i < length ; i++ ) {
  828.     if ( str[i] == ' ' ) {
  829.         last_space = i ;
  830.     }
  831.     if ( col == 79 ) {
  832.         str[last_space] = '\n' ;
  833.         col = i - last_space ;
  834.         last_space = 0 ;
  835.     } else {
  836.         col++ ;
  837.     }
  838.     }
  839. }
  840.  
  841. #ifdef    DISPLAY
  842. /* ================================= display routines ====================== */
  843. /* Currently for HP Starbase - pretty easy to modify */
  844. void DisplayPolygon( pgon, numverts, id )
  845. double    pgon[][2] ;
  846. int    numverts ;
  847. {
  848. static    int    init_flag = 0 ;
  849. int    i ;
  850. char    str[256] ;
  851.  
  852.     if ( !init_flag ) {
  853.     init_flag = 1 ;
  854.     /* make things big enough to avoid clipping */
  855.     Display_Scale = 0.45 / ( Vertex_Radius + Vertex_Perturbation ) ;
  856.     Display_OffsetX = Display_Scale + 0.05 ;
  857.     Display_OffsetY = Display_Scale + 0.10 ;
  858.  
  859.     Fd = DevOpen(OUTDEV,INIT) ;
  860.     shade_mode( Fd, CMAP_FULL|INIT, 0 ) ;
  861.     background_color( Fd, 0.1, 0.2, 0.4 ) ;
  862.     line_color( Fd, 1.0, 0.9, 0.7 ) ;
  863.     text_color( Fd, 1.0, 1.0, 0.2 ) ;
  864.     character_height( Fd, 0.08 ) ;
  865.     marker_type( Fd, 3 ) ;
  866.     }
  867.     clear_view_surface( Fd ) ;
  868.  
  869.     move2d( Fd,
  870.     (float)( pgon[numverts-1][X] * Display_Scale + Display_OffsetX ),
  871.     (float)( pgon[numverts-1][Y] * Display_Scale + Display_OffsetY ) ) ;
  872.     for ( i = 0 ; i < numverts ; i++ ) {
  873.     draw2d( Fd,
  874.         (float)( pgon[i][X] * Display_Scale + Display_OffsetX ),
  875.         (float)( pgon[i][Y] * Display_Scale + Display_OffsetY ) ) ;
  876.     }
  877.  
  878.     sprintf( str, "%4d sides, %3d of %d\n", numverts, id+1, Test_Polygons ) ;
  879.     text2d( Fd, 0.01, 0.01, str, VDC_TEXT, 0 ) ;
  880.     flush_buffer( Fd ) ;
  881. }
  882.  
  883. void DisplayPoint( point, hilit )
  884. double    point[2] ;
  885. int    hilit ;
  886. {
  887. float    clist[2] ;
  888.  
  889.     if ( hilit ) {
  890.     marker_color( Fd, 1.0, 0.0, 0.0 ) ;
  891.     } else {
  892.     marker_color( Fd, 0.2, 1.0, 1.0 ) ;
  893.     }
  894.  
  895.     clist[0] = (float)( point[0] * Display_Scale + Display_OffsetX ) ;
  896.     clist[1] = (float)( point[1] * Display_Scale + Display_OffsetY ) ;
  897.     polymarker2d( Fd, clist, 1, 0 ) ;
  898.     flush_buffer( Fd ) ;
  899. }
  900.  
  901. int DevOpen(dev_kind,init_mode)
  902. int dev_kind,init_mode;
  903. {
  904. char    *dev, *driver;
  905. int    fildes ;
  906.  
  907.     if ( dev_kind == OUTDEV ) {
  908.     dev = getenv("OUTINDEV");
  909.     if (!dev) dev = getenv("OUTDEV");
  910.     if (!dev) dev = "/dev/crt" ;
  911.     driver = getenv("OUTDRIVER");
  912.     if (!driver) driver = "hp98731" ;
  913.     } else {
  914.     dev = getenv("OUTINDEV");
  915.     if (!dev) dev = getenv("INDEV");
  916.     if (!dev) dev = "/dev/hil2" ;
  917.     driver = getenv("INDRIVER");
  918.     if (!driver) driver = "hp-hil" ;
  919.     }
  920.  
  921.     /* driver?    we don't need no stinking driver... */
  922.     fildes = gopen(dev,dev_kind,NULL,init_mode);
  923.  
  924.     return(fildes) ;
  925. }
  926. #endif
  927.